﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>
#include<assert.h>
#include<stdbool.h>
//分割链表
//给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
//你不需要 保留 每个分区中各节点的初始相对位置。
//示例 1：
//输入：head = [1, 4, 3, 2, 5, 2], x = 3
//输出：[1, 2, 2, 4, 3, 5]
//示例 2：
//输入：head = [2, 1], x = 2
//输出：[1, 2]

//typedef struct ListNode ListNode;
//struct ListNode* partition(struct ListNode* head, int x)
//{
//	if (head == NULL)
//	{
//		return head;
//	}
//	//创建两个带头链表
//	ListNode* lesshead, * lesstail;
//	ListNode* greaterhead, * greatertail;
//	lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));
//	greaterhead = greatertail = (ListNode*)malloc(sizeof(ListNode));
//
//	//遍历原链表，将原链表中的节点尾插到大小链表中
//	ListNode* pcur = head;
//	while (pcur)
//	{
//		if (pcur->val < x)
//		{
//			//尾插到小链表中
//			lesstail->next = pcur;
//			lesstail = lesstail->next;
//		}
//		else
//		{
//			//尾插到大链表中
//			greatertail->next = pcur;
//			greatertail = greartertail->next;
//		}
//		pcur = pcur - next;
//	}
//	//修改大链表中的尾节点的next指针指向
//	greatertail->next = NULL;//若不加这一行，代码会出现死循环+next指针初始化
//
//	//小链表的尾节点和大链表的第一个有效节点首尾相连
//	lesstail->next = greaterhead->next;
//}


//虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表
//1.⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。
//2.带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带
//来很多优势，实现反⽽简单了，后⾯我们代码实现了就知道了。


























































































